package leetcode_动态规划._07背包问题._01背包;

/**
 * @author yzh
 * @data 2021/3/18 14:28
 * 最后一块石头的重量 II
 * 每次取两块石头互相粉碎，最后剩余石头的最小重量
 * 思路：
 *   如果数组中的元素总和是偶数，则直接返回 0
 *   反之，则取总和除 2 后的数为背包容量
 *   这样就转化成了 01 背包问题
 */
public class _1049 {
    public static void main(String[] args) {
    }

    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int[] dp = new int[sum / 2 + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = sum / 2; j >= stones[i]; --j) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[sum / 2];
    }
}
